package pers.whj.util.list;

public class MinMaxHeapImpl<T> extends SeqList<T> implements MinMaxHeap<T> {
    public MinMaxHeapImpl() {
        super();
    }

    public MinMaxHeapImpl(int initLength) {
        super(initLength);
    }

    public MinMaxHeapImpl(T[] data) {
        super();
        if (data != null) {
            insert(0, data);
            adjust();
        }
    }

    @Override
    public boolean insert(T data) {
        if (super.insert(data)) {
            siftUp(mLength - 1);
            return true;
        }
        return false;
    }

    @Override
    public boolean insert(T[] data) {
        if (data == null) {
            return false;
        }
        if (mLength + data.length > getMaxLength() && !canResize()) {
            return false;
        }
        for (T tmp : data) {
            if (!insert(tmp)) {
                return false;
            }
        }
        return true;
    }

    @Override
    public T peek() {
        return data(0);
    }

    @Override
    public void adjust() {
        if (mLength > 1) {
            int i = (mLength - 2) / 2;
            while (i >= 0) {
                siftDown(i);
                i--;
            }
        }
    }

    @Override
    public T delete() {
        return deleteMin();
    }

    @Override
    public T deleteMin() {
        T data = data(0);
        mData[0] = mData[mLength - 1];
        super.delete();
        if (mLength > 1) {
            siftDownMin(0);
        }
        return data;
    }

    @Override
    @SuppressWarnings({"unchecked"})
    public T deleteMax() {
        if (mLength <= 2) {
            return super.delete();
        } else {
            int index = ((Comparable<T>) mData[1]).compareTo(data(2)) > 0 ? 1 : 2;
            T data = data(index);
            mData[index] = mData[mLength - 1];
            super.delete();
            siftDownMax(index);
            return data;
        }
    }

    @Override
    @SuppressWarnings({"unchecked"})
    public T peekMax() {
        if (mLength <= 2) {
            return data(mLength - 1);
        } else {
            return ((Comparable<T>) mData[1]).compareTo(data(2)) >= 0 ? data(1) : data(2);
        }
    }

    @Override
    public T peekMin() {
        return data(0);
    }

    @Override
    public int level(int index) {
        int k = (int) (Math.log(index + 1) / Math.log(2.0));
        return k % 2 == 1 ? LEVEL_MAX : LEVEL_MIN;
    }

    @SuppressWarnings({"unchecked"})
    private void siftUp(int i) {
        if (i > 0) {
            int p = (i - 1) / 2;
            Comparable<T> x = (Comparable<T>) mData[i];
            switch (level(p)) {
                case LEVEL_MIN:
                    if (x.compareTo(data(p)) < 0) {
                        mData[i] = mData[p];
                        mData[p] = x;
                        siftUpMin(p);
                    } else {
                        siftUpMax(i);
                    }
                    break;
                case LEVEL_MAX:
                    if (x.compareTo(data(p)) > 0) {
                        mData[i] = mData[p];
                        mData[p] = x;
                        siftUpMax(p);
                    } else {
                        siftUpMin(i);
                    }
                    break;
            }
        }
    }

    private void siftDown(int i) {
        if (level(i) == LEVEL_MIN) {
            siftDownMin(i);
        } else {
            siftDownMax(i);
        }
    }

    @SuppressWarnings({"unchecked"})
    private void siftUpMax(int i) {
        Comparable<T> x = (Comparable<T>) mData[i];
        for (int j = (i - 3) / 4; j > 0 && x.compareTo(data(j)) > 0; j = (j - 3) / 4) {
            mData[i] = mData[j];
            i = j;
        }
        mData[i] = x;
    }

    @SuppressWarnings({"unchecked"})
    private void siftUpMin(int i) {
        Comparable<T> x = (Comparable<T>) mData[i];
        for (int j = (i - 3) / 4; j >= 0 && x.compareTo(data(j)) < 0; j = (j - 3) / 4) {
            mData[i] = mData[j];
            i = j;
            if (j == 0) {
                break;
            }
        }
        mData[i] = x;
    }

    @SuppressWarnings({"unchecked"})
    private void siftDownMax(int i) {
        Comparable<T> x = (Comparable<T>) mData[i];
        int j = (mLength - 2) / 2;
        while (i <= j) {
            int k = maxChildIndexOfTwoLevels(i);
            if (k == -1 || x.compareTo(data(k)) >= 0) {
                break;
            } else {
                mData[i] = mData[k];
                if (k <= 2 * i + 2) {
                    i = k;
                    break;
                } else {
                    int p = (k - 1) / 2;
                    if (x.compareTo(data(p)) < 0) {
                        Object tmp = mData[p];
                        mData[p] = x;
                        x = (Comparable<T>) tmp;
                    }
                }
                i = k;
            }
        }
        mData[i] = x;
    }

    @SuppressWarnings({"unchecked"})
    private void siftDownMin(int i) {
        Comparable<T> x = (Comparable<T>) mData[i];
        int j = (mLength - 2) / 2;
        while (i <= j) {
            int k = minChildIndexOfTwoLevels(i);
            if (k == -1 || x.compareTo(data(k)) <= 0) {
                break;
            } else {
                mData[i] = mData[k];
                if (k <= 2 * i + 2) {
                    i = k;
                    break;
                } else {
                    int p = (k - 1) / 2;
                    if (x.compareTo(data(p)) > 0) {
                        Object tmp = mData[p];
                        mData[p] = x;
                        x = (Comparable<T>) tmp;
                    }
                }
                i = k;
            }
        }
        mData[i] = x;
    }

    @SuppressWarnings({"unchecked"})
    private int maxChildIndexOfTwoLevels(int i) {
        int[] tmp = {2 * i + 1, 2 * i + 2, 4 * i + 3, 4 * i + 4, 4 * i + 5, 4 * i + 6};
        if (tmp[0] >= mLength) {
            return -1;
        }
        int maxIndex = tmp[0];
        Comparable<T> maxValue = (Comparable<T>) mData[maxIndex];
        for (int j = 1; j < 6; j++) {
            if (tmp[j] < mLength) {
                if (maxValue.compareTo(data(tmp[j])) < 0) {
                    maxIndex = tmp[j];
                    maxValue = (Comparable<T>) mData[maxIndex];
                }
            } else {
                break;
            }
        }
        return maxIndex;
    }

    @SuppressWarnings({"unchecked"})
    private int minChildIndexOfTwoLevels(int i) {
        int[] tmp = {2 * i + 1, 2 * i + 2, 4 * i + 3, 4 * i + 4, 4 * i + 5, 4 * i + 6};
        if (tmp[0] >= mLength) {
            return -1;
        }
        int minIndex = tmp[0];
        Comparable<T> minValue = (Comparable<T>) mData[minIndex];
        for (int j = 1; j < 6; j++) {
            if (tmp[j] < mLength) {
                if (minValue.compareTo(data(tmp[j])) > 0) {
                    minIndex = tmp[j];
                    minValue = (Comparable<T>) mData[minIndex];
                }
            } else {
                break;
            }
        }
        return minIndex;
    }
}